package com.study.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

//https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
public class Solution_102 {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        Map<Integer, List<Integer>> levelMap = new HashMap<>();
        levelOrder(root, 0, levelMap);
        for (int i = 0; i < levelMap.size(); i++) {
            result.add(levelMap.get(i));
        }
        return result;
    }

    public void levelOrder(TreeNode node, int level, Map<Integer, List<Integer>> levelMap) {
        if (node == null) {
            return;
        }
        if (levelMap.get(level) == null) {
            List<Integer> levelList = new ArrayList<>();
            levelMap.put(level, levelList);
        }
        levelMap.get(level).add(node.val);
        if (node.left != null) {
            levelOrder(node.left, level + 1, levelMap);
        }
        if (node.right != null) {
            levelOrder(node.right, level + 1, levelMap);
        }
    }
}
